package year2023.recursion;

/*
集合的非空子集

请编写一个方法，返回某集合的所有非空子集。

给定一个int数组A和数组的大小int n，请返回A的所有非空子集。

保证A的元素个数小于等于20，且元素互异。

 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Code05_NonvoidSubset {

    public static void main(String[] args) {
        int[] A = {1,2,3};
        Code05_NonvoidSubset obj = new Code05_NonvoidSubset();
        Set<Set<Integer>> res = obj.getSubsets3(A, A.length);
        System.out.println(res);
        Set<Set<Integer>> res1 = obj.getSubsets2(A, A.length);
        System.out.println(res1);

        ArrayList<ArrayList<Integer>> res2 = obj.getSubsets(A, A.length);
        System.out.println(res2);

    }
    /**
     * 增量构造法
     * @param A
     * @param n
     * @return
     */
    public Set<Set<Integer>> getSubsets3(int[] A, int n){
        //Arrays.sort(A);
        return getSubsets3Core(A, n, n - 1);
    }

    /**
     * 递归增量构造法
     * @param A
     * @param n
     * @param cur
     * @return
     */
    private Set<Set<Integer>> getSubsets3Core(int[] A, int n, int cur){
        Set<Set<Integer>> newSet = new HashSet<>();
        if (cur == 0){//处理第一个元素
            Set<Integer> nulls = new HashSet<>();//空集
            Set<Integer> first = new HashSet<>();//包含第一个元素的集合
            first.add(A[0]);
            newSet.add(nulls);
            newSet.add(first);
            return newSet;
        }
        Set<Set<Integer>> oldSet = getSubsets3Core(A, n, cur - 1);


        for (Set<Integer> set : oldSet) {
            //对于每个子集, cur这个元素可以加进去,也可以不加进去
            newSet.add(set);//保留原样
            Set<Integer> clone = (Set<Integer>) ((HashSet)set).clone();
            clone.add(A[cur]);//添加当前元素
            newSet.add(clone);
        }
        return newSet;
    }

    //iteration
    public Set<Set<Integer>> getSubsets2(int[] A, int n){
        Set<Set<Integer>> res = new HashSet<>();
        res.add(new HashSet<>());//初始化为空集

        //从第一个元素开始处理
        for (int i = 0; i < n; i++) {
            Set<Set<Integer>> res_new = new HashSet<>();//新建一个大集合
            res_new.addAll(res);//把原来集合中的每个子集都加入到新的集合中
            //遍历之前的集合，对于当前元素可以加进去或者不加进去
            for (Set e : res) {
                Set a = (Set) ((HashSet) e).clone();
                a.add(A[i]);//把当前元素加进去
                res_new.add(a);
            }
            res = res_new;
        }
        return res;
    }

    //binary system
    public ArrayList<ArrayList<Integer>> getSubsets(int[] A, int n){
        Arrays.sort(A);//正序排序
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();//大集合

        for (int i = (int)Math.pow(2,A.length) - 1; i > 0; i--){
            ArrayList<Integer> s = new ArrayList<>();//对每个i建立一个集合
            for (int j = n - 1; j >= 0; j--){
                if (((i >> j) & 1) == 1){//检查哪个位上的二进制为1
                    s.add(A[j]);
                }
            }
            res.add(s);
        }
        return res;
    }

}
